/*
9.23 用链表和队列的二路归并排序，保证链表头不变
date:20201230 pm 11:04
key:1.遍历原链表时，只是把子序列的头提取了出来，本质上还是连一起。所以要及时切断尾巴。
	2.注意二路归并循环结束的条件
	3.注意我们在归并的时候为了保留最开始的头结点，希望总是以头结点为a参与归并，即归并结果马上参与下一个归并，由于C++队列不能插入队头，因此用一个栈中转至另一个栈，通过栈的特性完成这个要求。
*/
#include<iostream>
#include<queue>
#include<stack>

using namespace std;
class node
{
public:
	int value;
	node* next;
	node()
	{
		value = -1;
		next = NULL;
	}
};
void print(node* head)
{
	node* p = head;
	while (p != NULL)
	{
		cout << p->value;
		if (p->next != NULL)
		{
			if (p->next->value == -1)
			{
				p->next = NULL;
				break;
			}
		}

		p = p->next;
	}
	cout << "\n";
}
node* GuiBingSort(node* p1, node* p2)
{
	queue<int>q1;
	queue<int>q2;
	queue<int>q3;
	node* p = p1;
	//将两个链表的东西装进两个队列
	while (p != NULL)
	{
		
		q1.push(p->value);		
		p = p->next;
	}
	p = p2;
	while (p != NULL)
	{

		q2.push(p->value);
		p = p->next;
	}
	//二路归并，注意只要有一个不空就继续
	while (!q1.empty() || !q2.empty())
	{
		//当有其中一个是空的时候
		if (q1.empty() || q2.empty())
		{
			if (q1.empty())
			{
				while (!q2.empty())
				{
					q3.push(q2.front());
					q2.pop();
				}
			}
			if (q2.empty())
			{
				while (!q1.empty())
				{
					q3.push(q1.front());
					q1.pop();
				}
			}
		}
		else//都不空
		{
			if (q1.front() > q2.front())
			{
				q3.push(q2.front());
				q2.pop();
			}
			else
			{
				q3.push(q1.front());
				q1.pop();
			}
		}
	}
	//按题目意思保留p1指针给你
	p = p1;
	while (!q3.empty())
	{
		
		p->value = q3.front();
		q3.pop();
		//保证没有-1
		if (!q3.empty())
		{
			if (p->next == NULL)
			{
				p->next = new node;
			}
			p = p->next;
		}

	}
	return p1;
}
void divide(node* head)
{
	queue<node*>q1;
	stack<node*>s1;
	stack<node*>s2;
	node* p = head;
	node* p2 = head;
	q1.push(head);
	//遍历单链表，因为想从小到大的排序，如果后一个值比前一个小，则记录这个指向后一个的指针。
	while (p->next != NULL)
	{
		if (p->next->value != -1)
		{	
			p2 = p->next;;
			if (p->value > p->next->value)
			{
				q1.push(p->next);//只是把子序列的头提取了出来，本质上还是连一起
				p->next = NULL;
			}
			p = p2;
		}

	}
	////若干有子链表头的值输出显示,这段代码把q1搬空了直接
	//cout <<  "若干有子链表头的值输出显示";
	//while (!q1.empty())
	//{
	//	cout<<q1.front()->value<<" ";
	//	q1.pop();
	//}
	//因为c++队列无法在队头插入,所以搞了两个栈。
	while (!q1.empty())
	{
		s1.push(q1.front());
		q1.pop();
	}
	while (!s1.empty())
	{
		s2.push(s1.top());
		s1.pop();
	}
	//最开始head是先放进去的，这里也是a代表head，因此头指针没没改变。
	node* a;
	node* b;
	while (s2.size() > 1)
	{
		a = s2.top();
		s2.pop();
		b = s2.top();
		s2.pop();
		s2.push(GuiBingSort(a, b));
	}
	
}
int main()

{

	int N, M, i, j, k, l;
	node* head_r = new node;
	node* p = head_r;
	cout << "排序数组大小" << endl;
	cin >> N ;
	cout << "排序数组" << endl;
	//输入N个数字 10 9 1 2 8 3 7 4 6 5 0
	int*A = new int [N];
	//尾指针是-1
	for (i = 0; i < N; i++)
	{
		cin>>p->value;
		p->next = new node;
		p = p->next;
	}
	//遍历链表并去掉尾哨兵
	cout << "遍历链表并去掉尾哨兵" << endl;
	print(head_r);
	//
	divide(head_r);
	cout << "同一个头节点遍历链表" << endl;
	print(head_r);
}